#include<stdio.h>
#include<time.h>

// 70、爬楼梯，https://leetcode.cn/problems/climbing-stairs/description/
// 优化时间复杂度
// 使用map，保存已经算过的爬n级台阶的方法数

int size = 10;

// i = 0, 爬1级台阶
// i, 爬i+1级台阶
int arr[20] = {0};

int numsWay(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return numsWay(n - 1) + numsWay(n - 2);
}

int numsWay2(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;

  if (arr[n - 1] != 0) {
    return arr[n - 1];
  }

  arr[n - 1] = numsWay2(n - 1) + numsWay2(n - 2);

  return arr[n - 1];
}

int main() {

  clock_t start, end;
  double time;

  start = clock();
  printf("n = 3, ret = %d\n", numsWay(3));
  printf("n = 4, ret = %d\n", numsWay(4));
  printf("n = 5, ret = %d\n", numsWay(5));
  printf("n = 10, ret = %d\n", numsWay(10));
  printf("n = 16, ret = %d\n", numsWay(16));
  end = clock();
  time = (double) (end - start) / CLOCKS_PER_SEC;
  printf("numsWay time = %lf\n", time);

  start = clock();
  printf("n = 3, ret = %d\n", numsWay2(3));
  printf("n = 4, ret = %d\n", numsWay2(4));
  printf("n = 5, ret = %d\n", numsWay2(5));
  printf("n = 10, ret = %d\n", numsWay2(10));
  printf("n = 16, ret = %d\n", numsWay2(16));
  end = clock();
  time = (double) (end - start) / CLOCKS_PER_SEC;
  printf("numsWay2 time = %lf\n", time);

  int i = 0;
  int len = sizeof(arr) / sizeof(arr[0]);
  while(i < len) {
    printf("    arr[%d] = %d \n", i, arr[i]);
    i++;
  }
}
